package algorithm;

/**
 * @Author: hujian
 * @Date: 2019/10/21 8:51
 * @Description: <描述>
 */
public class Test {
    /**
     * 方法功能：对单链表进行逆序输入参数：head：链表头结点
     */
    private static void reverse(Lnode head) {
        // 判断链表是否为空
        if (null == head || null == head.next) {
            return;
        }
        Lnode pre;   //前驱结点
        Lnode cur;   //当前结点
        Lnode next;  //后继结点
        // 把链表首结点变为尾结点
        cur = head.next;
        next = cur.next;
        cur.next = null;
        pre = cur;
        cur = next;
        // 使当前遍历到的结点cur指向前驱结点
        while (null != cur.next) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            //cur = cur.next;
            cur = next;
        }
        // 最后一个结点指向倒数第二个结点
        cur.next = pre;
        // 链表的头结点指向原来链表的尾结点
        head.next = cur;
    }

    private Lnode recursive(Lnode head) {
        if (null == head || null == head.next) {
            return head;
        } else {
            Lnode newhead = recursive(head.next);
            head.next.next = head;
            return newhead;
        }
    }

    @org.junit.Test
    public void test1() {
        // 链表头结点
        Lnode head = new Lnode();
        head.next = null;
        Lnode temp = null;
        Lnode cur = head;
        // 构造单链表
        for (int i = 1; i < 8; i++) {
            temp = new Lnode();
            temp.data = i;
            temp.next = null;
            cur.next = temp;
            cur = temp;
        }
        System.out.print("逆序前： ");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
        System.out.print("逆序后： ");
        //reverse(head);
        head = recursive(head.next);
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
    }
}
